package com.c2b.algorithm.newcoder;

/**
 * <a href='https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9?tpId=295&tqId=23286&ru=%2Fexam%2Foj&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj'>BM8 链表中倒数最后k个结点 </a>
 *
 * @author c2b
 * @since 2024/3/14 10:47
 */
public class BM8FindKthToTail {
    public static class Solution {
        public ListNode FindKthToTail(ListNode pHead, int k) {
            if (pHead == null) {
                return null;
            }
            // 快指针先行k步
            ListNode fast = pHead;
            for (int i = 1; i <= k; i++) {
                if (fast != null) {
                    fast = fast.next;
                } else {
                    // 达不到k步说明链表过短，没有倒数k
                    return null;
                }
            }
            // 快慢指针同步，快指针先到底，慢指针指向倒数第k个
            ListNode slow = pHead;
            while (fast != null) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode head = new ListNode(0);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        Printer.printListNode(solution.FindKthToTail(head, 5));
    }
}
